package day08;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/4/8 14:56
 */

import java.util.ArrayList;

/**
 * 欢迎各位来到「力扣嘉年华」，接下来将为各位介绍在活动中广受好评的弹珠游戏。
 *
 * N*M 大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate 中，数组中的每个元素为仅由 "O"、"W"、"E"、"." 组成的字符串。其中：
 *
 * "O" 表示弹珠洞（弹珠到达后会落入洞中，并停止前进）；
 * "W" 表示逆时针转向器（弹珠经过时方向将逆时针旋转 90 度）；
 * "E" 表示顺时针转向器（弹珠经过时方向将顺时针旋转 90 度）；
 * "." 表示空白区域（弹珠可通行）。
 * 游戏规则要求仅能在边缘位置的 空白区域 处（弹珠盘的四角除外）沿 与边缘垂直 的方向打入弹珠，并且打入后的每颗弹珠最多能 前进 num 步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 按任意顺序 返回答案。
 *
 * 注意：
 *
 * 若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进，则将直接出界。
 * 示例 1：
 *
 * 输入： num = 4 plate = ["..E.",".EOW","..W."]
 *
 * 输出：[[2,1]]
 *
 * 解释： 在 [2,1] 处打入弹珠，弹珠前进 1 步后遇到转向器，前进方向顺时针旋转 90 度，再前进 1 步进入洞中。b054955158a99167b8d51da0e22a54da.gif
 *
 * 示例 2：
 *
 * 输入： num = 5 plate = [".....","..E..",".WO..","....."]
 *
 * 输出：[[0,1],[1,0],[2,4],[3,2]]
 *
 * 解释： 在 [0,1] 处打入弹珠，弹珠前进 2 步，遇到转向器后前进方向逆时针旋转 90 度，再前进 1 步进入洞中。 在 [1,0] 处打入弹珠，弹珠前进 2 步，遇到转向器后前进方向顺时针旋转 90 度，再前进 1 步进入洞中。 在 [2,4] 处打入弹珠，弹珠前进 2 步后进入洞中。 在 [3,2] 处打入弹珠，弹珠前进 1 步后进入洞中。b44e9963239ae368badf3d00b7563087.gif
 *
 * 示例 3：
 *
 * 输入： num = 3 plate = [".....","....O","....O","....."]
 *
 * 输出：[]
 *
 * 解释： 由于弹珠被击中后只能前进 3 步，且不能在弹珠洞和弹珠盘四角打入弹珠，故不存在能让弹珠入洞的打入位置。
 */
public class Solution4 {
    private static int[][] D = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

    public int[][] ballGame(int num, String[] plate) {
        ArrayList<int[]> list = new ArrayList<>();
        for (int i = 1; i < plate.length - 1; i++) {
            if (plate[i].charAt(0) == '.' && ballGame(i, 0, 0, num, plate)) {
                list.add(new int[] { i, 0 });
            }
            if (plate[i].charAt(plate[0].length() - 1) == '.' && ballGame(i, plate[0].length() - 1, 2, num, plate)) {
                list.add(new int[] { i, plate[0].length() - 1 });
            }
        }
        for (int i = 1; i < plate[0].length() - 1; i++) {
            if (plate[0].charAt(i) == '.' && ballGame(0, i, 1, num, plate)) {
                list.add(new int[] { 0, i });
            }
            if (plate[plate.length - 1].charAt(i) == '.' && ballGame(plate.length - 1, i, 3, num, plate)) {
                list.add(new int[] { plate.length - 1, i });
            }
        }
        int[][] result = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    private boolean ballGame(int x, int y, int i, int k, String[] plate) {
        if (x < 0 || y < 0 || x >= plate.length || y >= plate[0].length() || k < 0) {
            return false;
        } else if (plate[x].charAt(y) == 'O') {
            return true;
        } else if (plate[x].charAt(y) == 'W') {
            return ballGame(x + D[(i + 3) % 4][0], y + D[(i + 3) % 4][1], (i + 3) % 4, k - 1, plate);
        } else if (plate[x].charAt(y) == 'E') {
            return ballGame(x + D[(i + 1) % 4][0], y + D[(i + 1) % 4][1], (i + 1) % 4, k - 1, plate);
        }
        return ballGame(x + D[i][0], y + D[i][1], i, k - 1, plate);
    }
}
